package com.example.tencentTrain;

import com.example.tree.TreeNode;

public class Leetcode236_LowestCommonAncestor {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        TreeNode p = root.left;
        TreeNode q = root.right;
        System.out.println(new Solution().lowestCommonAncestor(root, p, q).val);


    }

    static class Solution {

        /**
         * 若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：
         *   1. p 和 q 在 root 的子树中，且分列root 的 异侧（即分别在左、右子树中）；
         *   2.p = root ，且 q 在 root 的左或右子树中；
         *   3. q = root ，且 p 在 root 的左或右子树中；
         *
         * @param p
         * @param q
         * @return
         */
        private TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q) return root; // 情况2、3直接返回即可
            TreeNode left = lowestCommonAncestor1(root.left, p, q);
            TreeNode right = lowestCommonAncestor1(root.right, p, q);
            if(left == null && right == null) return null;
            if(left == null) return right;
            if(right == null) return left;
            return root;
        }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            return lowestCommonAncestor1(root, p, q);
        }
    }
}
